/**
 * 两个字符串间的最短路径
 * https://fcqian.blog.csdn.net/article/details/134759904?spm=1001.2014.3001.5502
 * 思路：
 * 这题的思路是动态规划
1. 每一个点的最短距离，是能触达到它的（左上？->如果可以的话，上，左三个方向的点的最短路径+1）
2. 从矩阵左上角开始，逐行往下递增，直到右下角
 */

class StringPath {
    constructor(strA, strB) {
        this.strA = strA.toUpperCase(); // 转大写
        this.strB = strB.toUpperCase(); // 转大写
        this.cols = this.strA.length + 1;
        this.rows = this.strB.length + 1;

        // 构建最短路径数组
        this.dist = new Array(this.rows).fill(true).map(() => {
            return new Array(this.cols).fill(-1);
        });

        // 最短路径初始化
        // 第一行每个点的最短距离来自左边
        // 第一列每个点的最短距离来自上边
        this.dist[0].forEach((_, i) => {
            this.dist[0][i] = i;
        });
        this.dist.forEach((_, i_r) => {
            this.dist[i_r][0] = i_r;
        });

        // console.log(
        //     `[StringPath] dist array inited: ${JSON.stringify(this.dist)}`
        // );

        const result = this.getResult();
        console.log(`[StringPath] ${strA} ${strB} shortest is ${result}`);
    }

    getResult() {
        let { strA, strB, rows, cols, dist } = this;

        for (let row = 1; row < rows; row++) {
            for (let col = 1; col < cols; col++) {
                // 上
                const distUp = dist[row - 1][col];
                // 左
                const distLeft = dist[row][col - 1];
                // 左上
                let distLeftUp = Number.MAX_SAFE_INTEGER;
                if (strA[col - 1] === strB[row - 1]) {
                    distLeftUp = dist[row - 1][col - 1];
                }

                dist[row][col] = Math.min(distLeft, distUp, distLeftUp) + 1;
            }
        }

        console.log(`[getResult] final dist is`);

        dist.forEach((row) => {
            console.log(JSON.stringify(row));
        });

        return dist[rows - 1][cols - 1];
    }
}

new StringPath('abc', 'abc');
new StringPath('abc', 'cba');
new StringPath('abcabba', 'cbabac');
